package com.tlvip.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>description：</p>
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>
 * 前序遍历二叉树
 * 中序遍历二叉树
 * 后序遍历二叉树
 * 层序遍历二叉树
 * 线索中序二叉树
 * <p>instructions： </p>
 * Date 2022/6/16</p>
 * Author mac
 *
 * @version 1.0
 */
public class TraversingBinaryTree {

    public static void main(String[] args) {
        TreeNode root = initTree();
        System.out.println("前序遍历二叉树：");
        preOrder(root);
        System.out.println();
        System.out.println("中序遍历二叉树：");
        midOrder(root);
        System.out.println();
        System.out.println("后序遍历二叉树：");
        afterOrder(root);
        System.out.println();
        System.out.println("层序遍历二叉树：");
        List<Integer> list = new ArrayList<>();
        levelOrder(root, 1, list);
        list.stream().forEach(o -> System.out.print(o + ","));
    }

    /**
     * 层序遍历
     *
     * @param root 根节点
     * @param i    下标
     * @param list 保存结果
     */
    public static void levelOrder(TreeNode root, int i, List<Integer> list) {
        if (root == null) {
            return;
        }
        int length = list.size();
        if (length <= i) {
            for (int j = 0; j <= i - length; j++) {
                list.add(length + j, null);
            }
        }
        list.set(i, root.getVal());
        levelOrder(root.getLeft(), 2 * i, list);
        levelOrder(root.getRight(), 2 * i + 1, list);
    }

    /**
     * 后序遍历
     *
     * @param root 根节点
     */
    public static void afterOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        afterOrder(root.getLeft());
        afterOrder(root.getRight());
        System.out.print(root.getVal() + ",");
    }

    /**
     * 中序遍历二叉树
     *
     * @param root 根节点
     */
    public static void midOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        midOrder(root.getLeft());
        System.out.print(root.getVal() + ",");
        midOrder(root.getRight());
    }


    /**
     * 前序遍历二叉树
     *
     * @param root 根节点
     */
    public static void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.getVal() + ",");

        if (root.getLeft() != null) {
            preOrder(root.getLeft());
        }
        if (root.getRight() != null) {
            preOrder(root.getRight());
        }
    }

    public static TreeNode initTree() {
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, null, null);
        TreeNode node5 = new TreeNode(5, node6, node7);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        return new TreeNode(1, node2, node3);
    }


    static class TreeNode {
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
